package main

import "fmt"

// 异或
// 满足交换律、结合律
// a ^ a = 0
// 0 ^ a = a
func main() {
	var nums []int = []int{1, 1, 2, 2, 9, 9, 9, 11, 11, 23, 23}
	res := OneOddNumber(nums)
	fmt.Println(res)

	var nums2 []int = []int{1, 1, 1, 2, 2, 9, 9, 9, 11, 11, 23, 23}
	res2, res3 := TwoOddNumber(nums2)
	fmt.Println(res2, res3)
}

// 数组中只有一个数字出现的次数是奇数次
// 其余数字出现的次数都是偶数次，找出该数字
func OneOddNumber(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	var res int = nums[0]
	for i := 1; i < len(nums); i++ {
		res = res ^ nums[i]
	}
	return res
}

// 数组中有两个数字出现的次数是奇数次
// 其余数字出现的次数都是偶数次，找出这两个数字
func TwoOddNumber(nums []int) (a, b int) {
	if len(nums) <= 1 {
		return 0, 0
	}
	var eor, eor2, res int
	// eor的最后结果为两个出现次数为奇数次的异或结果
	for i := 0; i < len(nums); i++ {
		eor = eor ^ nums[i]
	}
	// 因为这两个数字不相同，所以eor不为0
	// 所以eor肯定至少有一位是1
	// 且两个数字在该位的数字肯定不是相同的
	// 通过eor为1的那位将所有数字分为两组
	// eor2为提取最右侧的1，比如eor为100100，则eor2=000100
	// 其实取哪个1都是一样的
	eor2 = eor & (^eor + 1)
	for i := 0; i < len(nums); i++ {
		if nums[i]&eor2 == 0 {
			res = res ^ nums[i]
		}
	}
	return res, res ^ eor

}
